package com.javabasic.algorithm.sword_of_offer;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
import java.util.Queue;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see
 * @since Created by work on 2022/1/11 12:08 上午
 */
public class 剑指_Offer_32_II_从上到下打印二叉树_II {

    /**
     * BFS + 步长记录
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();

        if (root == null) {
            return result;
        }

        Queue<NewTreeNode> queue = new LinkedList<>();
        NewTreeNode currentNode = new NewTreeNode(root, 0), tempNode;
        queue.offer(currentNode);
        int deep;
        TreeNode temp;
        List<Integer> numList;
        while (!queue.isEmpty()) {
            currentNode = queue.poll();
            deep = currentNode.deep;
            if (result.size() > deep) {
                numList = result.get(deep);
            } else {
                numList = new ArrayList<>();
                result.add(numList);
            }
            temp = currentNode.node;
            numList.add(temp.val);
            if (temp.left != null) {
                tempNode = new NewTreeNode(temp.left, deep + 1);
                queue.offer(tempNode);
            }
            if (temp.right != null) {
                tempNode = new NewTreeNode(temp.right, deep + 1);
                queue.offer(tempNode);
            }
        }

        return result;


    }

    class NewTreeNode {
        TreeNode node;
        int deep;

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            NewTreeNode that = (NewTreeNode) o;
            return deep == that.deep && Objects.equals(node, that.node);
        }

        @Override
        public int hashCode() {
            return Objects.hash(node, deep);
        }

        public TreeNode getNode() {
            return node;
        }

        public void setNode(TreeNode node) {
            this.node = node;
        }

        public int getDeep() {
            return deep;
        }

        public void setDeep(int deep) {
            this.deep = deep;
        }

        public NewTreeNode(TreeNode node, int deep) {
            this.node = node;
            this.deep = deep;
        }
    }
}
